Computer modeling of a 3-dimensional space usually begins by defining a collection of "objects" existing within the space and maintaining this collection within a data base. The "definition" of an object includes enough information to allow a computer to draw, or render, the object from any perspective. Each object's location in "object space" coordinates is specified as well.
These objects are usually described in terms of vertices which define polygons in 3-dimensional object space. These polygons are then projected into a 2-dimensional image space, and drawn into a frame buffer which is used to display the polygons on a computer display.
Typically, a z-buffer is used to hide more distant objects behind objects nearer to the point of view. The z-buffer has an entry corresponding to each pixel in a frame buffer. While the frame buffer contains pixel color/intensity information, the z-buffer maintains a relative depth of each pixel. Before a pixel is overwritten in either buffer, a new pixel's depth is compared with the old (z-buffer) pixel's depth value. If the new pixel is closer, the frame buffer and z-buffer pixels are overwritten. Otherwise, the new pixel is discarded. In this manner, closer objects are displayed while objects obscured from view are not. While the actual z-buffer algorithm is usually implemented in hardware, all objects must first be processed, e.g. projected into 2-dimensional space and colored/textured, in order to be passed to the z-buffer, even though many of these objects are ultimately hidden. This is a very time-consuming and wasteful task.
Greene (U.S. Pat. No. 5,600,763), among others, attempts to improve on this by culling objects in image space. Greene does so by progressively subdividing the object space into smaller and smaller cubic spaces until either a size limit is reached or a cube is found to be the smallest cube that fully encloses a particular object. Greene tests for visibility of the cubes in image space, starting with the largest cube, and if that cube is visible, testing the sub-cubes therein, and so forth. Cubes that are not visible are culled before their associated objects are rendered. This would require significant modification to existing current graphics workstations.
Previous work by one of the present inventors, "Visibility Preprocessing For Interactive Walkthroughs", Teller and Sequin, Computer Graphics, Vol. 25, No. 4, July 1991, pp. 61-69, incorporated herein by reference, describes a process in which the "world" is divided early in the process into cells which have viewing portals into other cells. At start-up, it is determined for each cell which other cells are visible from the given cell. This information is maintained statically and allows culling of all cells (and objects therein) which are not visible from the cell holding the current viewpoint. As a refinement, a "view cone" is calculated to further dynamically cull cells that are not actually visible from the viewpoint as the viewpoint moves around. While this algorithm works well for architectural walk-throughs, it is not efficient for models with less apparent cell/portal structures such as outdoor city models.